#include <iostream>
#include <cstdio>
using namespace std;

int maze[5][5] = {
    {0, 1, 0, 0, 0},
    {0, 1, 0, 1, 0},
    {0, 0, 0, 0, 0},
    {0, 1, 1, 1, 0},
    {0, 0, 0, 1, 0},
};

#define ROW 5
#define COLUMN 5
#define ROAD 0
#define WALL 1
#define PASS 2

typedef struct
{
    /* data */
    int x;
    int y;
} loc_in_maze;

loc_in_maze path[25];
int path_flag = 0;

int d_x[4] = {0, 1, 0, -1};
int d_y[4] = {1, 0, -1, 0};

void print_path()
{
    int i;
    cout << " (0,0)";
    for (i = 0; i < path_flag; i++)
    {
        cout << "-> (" << path[i].x << "," << path[i].y << ")";
    }
    cout << endl;
}

void dfs_maze(int loc_x, int loc_y, int maze[ROW][COLUMN])
{
    int k;
    for (k = 0; k < 4; k++)
    {
        if (loc_x + d_x[k] >= 0 && loc_x + d_x[k] < 5 && loc_y + d_y[k] >= 0 && loc_y + d_y[k] < 5 && maze[loc_x + d_x[k]][loc_y + d_y[k]] == 0)
        {
            maze[loc_x + d_x[k]][loc_y + d_y[k]] = 2;
            path[path_flag].x = loc_x + d_x[k];
            path[path_flag].y = loc_y + d_y[k];
            path_flag++;
            if (loc_x + d_x[k] == 4 && loc_y + d_y[k] == 4)
            {
                print_path();
                exit(0);
            }
            else
            {
                dfs_maze(loc_x + d_x[k], loc_y + d_y[k], maze);
            }
            maze[loc_x + d_x[k]][loc_y + d_y[k]] = 0;
            path[path_flag].x = 0;
            path[path_flag].y = 0;
            path_flag--;
        }
    }
}
int main()
{
    dfs_maze(0, 0, maze);
    return 0;
}
